/**
 * Created with IntelliJ IDEA.
 * Description:
 * User: 23735
 * Date: 2023-05-30
 * Time: 23:17
 */
public class Solution {
    public double myPow(double x, int n) {
        // 使用 long 是因为 如果 n = - 2^32 时, -n 无法表示
        long count = n;
        return count < 0 ? 1 / quickMul(x, -count) : quickMul(x, count);
    }

    /**
     快速幂算法  x^n * x^n = x^2n
     比如要算 x^37  x^37 -> x^18 -> x^9 -> x^4 -> x^2 -> x
     但是 从 x^18 -> x^37, x^4 -> x^9 , 都多 * 了一个 x
     具体什么时候需要多 * 一个 x 呢,
     n 为奇数时, x^n = x^(n/2) * x^(n/2) * x
     n 为偶数时, x^n = x^(n/2) * x^(n/2)
     但是, 正着推是不容易推出来的, 所以需要使用递归
     使用递归就更容易看出来
     * @param x 底数
     * @param n 指数
     * @return
     */
    public double quickMul(double x, long n){
        // 递归终止条件
        if (n == 0) {
            return 1.0;
        }
        // 注意把中间结果记录下来, 不然超时
        double temp = quickMul(x, n/2);
        return n % 2 == 0 ? temp * temp : temp * temp * x;
    }
}
